1. Field of the Invention
The present invention relates generally to so-called “hidden-line removal” for erasing hidden lines when a three-dimensional model including a plurality of polygons is projected onto a two-dimensional plane, and more particularly to a hidden-line removal method in which processes are executed with memory consumption optimized.
2. Description of the Related Art
When a three-dimensional shape created by computer graphics is printed on a paper sheet or displayed on a display, an image is produced by extracting the ridge lines and outlines and projecting them onto a two-dimensional plane. In this case, when the three-dimensional shape is looked at from a viewpoint, so-called “hidden-line removal” and “hidden-face removal” are executed, in which ridge lines and outlines that can not be looked at actually due to the figures obscuring them are erased or those lines are represented by dotted lines.
As hidden-line (face) removal, when the three-dimensional shape is constituted as an aggregate of polygons, Z-sort method in which the depth value (Z value) is calculated for each polygon and an image is drawn sorting the polygons in the order of their Z values, and Z-buffer method in which a figure having a smaller Z value (the closest figure) is drawn into a frame buffer for each pixel, are known. In addition, methods that have been proposed include a method in which production of an image for which hidden faces have been removed is arranged to be executed at a high speed by dividing the screen into rectangular blocks and repeating production of a block image for which hidden faces have been removed (see Japanese Patent Application Laid-Open Publication No. 1997-179999), a method in which a high accuracy drawing process is realized by dividing the shape into a plurality of blocks according to their Z values and executing sorting of the blocks as well as executing sorting within each block (see Japanese Patent Application Laid-Open Publication No. 1998-134204), a method in which determination of the order of the depth and hidden-face removal are executed at a high-speed by dividing the spatial area into rectangular parallelepipeds, dividing further each rectangular parallelepiped into tetrahedrons and obtaining equivalent function value curved surface using approximation (Japanese Patent Application Laid-Open Publication No. 1995-92838) and a method in which data are processed at a high accuracy by solving mathematically the decision of crossing of ridge lines and outlines over polygons.